转自 http://blog.csdn.net/lych_cys/article/details/50983759
 实际上分块和分治的思想是差不多的，就直接讲分治吧。。

        首先转离线操作，然后对于某一个矩形区间x∈[lx,rx]，y∈[ly,ry]，然后要求出所有源点和汇点都在其中的询问，且路径不超出所在区间的答案。不妨设rx-lx>ly-ty，那么对x坐标进行分治，即将这个区间分成两块，那么对于某一个询问，有两种情况：

       1.如果询问的起点和终点在两个不同的块，那么一定会经过中轴线上的一点；

       2.如果在同一块，那么有可能经过中轴线；也有可能路径只在那一块中，就可以递归分治了；

       那么对于某一块，求出中轴线到所在块的所有点的距离，更新一下答案；然后递归分治。

       考虑用dijkstra+heap跑最短路，那么就大概是O(N^1.5logN)的（因为思想和kd-tree是差不多的吧所以时间也一样）。本地测试后两个点dijkstra+heap的时间接近spfa的一半